1. Field of the Invention
The present invention relates to computer networks and more particularly to maintaining Interior Gateway Protocol (IGP) transparency of Virtual Private Network (VPN) routes when Border Gateway Protocol (BGP) is used as a Provider Edge Device (PE) to Customer Edge Device (CE) protocol in a computer network.
2. Background Information
A computer network is a geographically distributed collection of interconnected subnetworks, such as local area networks (LAN), that transport data between network nodes. As used herein, a network node is any device adapted to send and/or receive data in the computer network. Thus, in the context of this disclosure, the terms “node” and “device” may be used interchangeably. The network topology is defined by an arrangement of network nodes that communicate with one another, typically through one or more intermediate network nodes, such as routers and switches. In addition to intra-network communications between network nodes located in the same network, data also may be exchanged between nodes located in different networks. To that end, an “edge device” located at the logical outer-bound of a first computer network may be adapted to send and receive data with an edge device situated in a neighboring (i.e., adjacent) network. Inter-network and intra-network communications are typically effected by exchanging discrete packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how network nodes interact with each other.
Each data packet typically comprises “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables network nodes to efficiently route the packet through the computer network. Often, a packet's network headers include a data-link (layer 2) header, an internetwork (layer 3) header and a transport (layer 4) header as defined by the Transmission Control Protocol/Internet Protocol (TCP/IP) Reference Model. The TCP/IP Reference Model is generally described in more detail in Section 1.4.2 of the reference book entitled Computer Networks, Fourth Edition, by Andrew Tanenbaum, published 2003, which is hereby incorporated by reference as though fully set forth herein.
A data packet may originate at a source node and subsequently “hop” from node to node along a logical data path until it reaches its destination. The network addresses defining the logical data path of a data flow are most often stored as Internet Protocol (IP) addresses in the packet's internetwork header. IP addresses are typically formatted in accordance with the IP Version 4 (IPv4) protocol, in which network nodes are addressed using 32 bit (four byte) values. Although IPv4 is prevalent in most networks today, IP Version 6 (IPv6) has been introduced to increase the length of an IP address to 128 bits (16 bytes), thereby increasing the number of available IP addresses. Typically, a network or subnetwork is allocated a predetermined set of IP addresses which may be assigned to network nodes situated within that network or subnetwork. Here, a subnetwork is a subset of a larger computer network, and thus network nodes in the subnetwork may be configured to communicate with nodes located in other subnetworks.
A subnet mask may be used to select a set of contiguous high-order bits from IP addresses within a subnetwork's allotted address space. A subnet mask length indicates the number of contiguous high-order bits selected by the subnet mask, and a subnet mask length of N bits is hereinafter represented as /N. The subnet mask length for a given subnetwork is typically selected based on the number of bits required to distinctly address nodes in that subnetwork. As used herein, an “address prefix” is defined as the result of applying a subnet mask to a network address, such as an IP address. An address prefix therefore specifies a range of network addresses in a subnetwork, and in IPv4 a/32 address prefix corresponds to a particular network address. A “route” is defined herein as an address prefix and its associated path attributes. The path attributes generally include any information that characterizes the address prefix, and may include various protocol-specific attributes, such as conventional Border Gateway Protocol attributes.
Interior Gateway Protocols (IGP)
A computer network may contain smaller groups of one or more subnetworks which may be managed as separate autonomous systems. As used herein, an autonomous system (AS) is broadly construed as a collection of interconnected network nodes under a common administration. Often, the AS is managed by a single administrative entity, such as a company, an academic institution or a branch of government. For instance, the AS may operate as an enterprise network, a service provider or any other type of network or subnetwork. Each AS is typically assigned a unique identifier, such as a unique AS number, that identifies the AS among a plurality of ASes in a computer network.
An AS may contain one or more edge devices (or “autonomous system border routers,” ASBRs), having peer connections to other edge devices located in adjacent networks or subnetworks. Thus, packets enter or exit the AS through an appropriate ASBR. The AS may be logically partitioned into a plurality of different “routing areas.” Each routing area includes a designated set of network nodes that are configured to share routing and topology information. As such, the network nodes in a routing area share a consistent “view” of the network topology. Since consistent sets of intra-area, inter-area, and inter-AS routing information are usually distributed among network nodes in an AS, the nodes can calculate consistent sets of “best paths” through the AS, e.g., using conventional shortest path first (SPF) calculations or other routing computations. A calculated best path corresponds to a preferred data path for transporting data between a pair of source and destination nodes. The best path may be an intra-area, inter-area, or inter-AS data path, depending on the locations of the source and destination nodes.
Area border devices, such as area border routers (ABR), are located at the logical border of two or more routing areas. Accordingly, each ABR device participates in multiple routing areas and typically maintains a separate set of routing and topology information for each adjacent routing area in which it participates. Each network node in a routing area typically maintains its own link-state database (LSDB). The LSDB is configured to store topology information advertised with the node's routing area. Because an ABR (by definition) participates in multiple routing areas, each ABR therefore maintains a separate LSDB for each of its routing areas.
Network nodes located in the same routing area generally exchange routing information and network-topology information using an “interior gateway” routing protocol (IGP), such as a link-state protocol. An example of a conventional link-state protocol is the Open Shortest Path First (OSPF) protocol, which is described in more detail in Request for Comments (RFC) 2328, entitled OSPF Version 2, dated April 1998, which is publicly available through the Internet Engineering Task Force (IETF) and is hereby incorporated by reference in its entirety.
OSPF employs conventional link-state advertisements (LSA) for exchanging routing and topology information between a set of interconnected intermediate network nodes, i.e., routers and switches. In fact, different types of LSAs may be used to communicate the routing and topology information. For example, the OSPF version 2 specification (RFC 2328) defines the following types of LSAs: Router, Network, Summary, and AS-External LSAs. Router and Network LSAs are used to propagate link information within a routing area. Specifically, Router LSAs advertise router-interface links (i.e., links connected to routers) and their associated cost values, whereas Network LSAs advertise network-interface links (i.e., links connected to subnetworks) and their associated cost values within the routing area.
Summary and AS-External LSAs are used to disseminate routing information between routing areas. The Summary LSA is typically generated by an ABR and is used to advertise intra-AS (“internal”) routes between routing areas. First, the ABR receives various LSAs that are advertised in a first routing area. The ABR “summarizes” the advertised routes by aggregating routes where possible. Next, the ABR stores the summarized routes in a Summary LSA, which it then advertises in a second routing area. In this way, nodes in the second area are made aware of routes in the first routing area that can be reached through the ABR. An AS-External LSA stores a list of reachable inter-AS (“external”) routes, i.e., located outside of the AS. The AS-External LSA is typically generated by an ASBR and is propagated throughout the AS to identify which external routes can be reached through the advertising ASBR. Unlike Summary LSAs, routes stored in an AS-External LSA are generally not aggregated.
PE-CE Network Topology
A virtual private network (VPN) is a collection of network nodes that establish private communications over a shared backbone network. Previously, VPNs were implemented by embedding private leased lines in the shared network. The leased lines (i.e., communication links) were reserved only for network traffic among those network nodes participating in the VPN. Today, the above-described VPN implementation has been mostly replaced by private “virtual circuits” deployed in public networks. Specifically, each virtual circuit defines a logical end-to-end data path between a pair of network nodes participating in the VPN.
Network nodes belonging to the same VPN may be situated in different subnetworks, or “customer sites.” Each customer site may participate in one or more different VPNs, although most often each customer site is associated with a single VPN, and hereinafter the illustrative embodiments will assume a one-to-one correspondence between customer sites and VPNs. For example, customer sites owned or managed by a common administrative entity, such as a corporate enterprise, may be statically assigned to the enterprise's VPN. As such, network nodes situated in the enterprise's various customer sites participate in the same VPN and are therefore permitted to securely communicate with one another.
The customer sites typically communicate with one another through a service provider network (“provider network”). The provider network is an AS that functions as a backbone network through which VPN information may be exchanged between customer sites. The provider network may include both provider edge devices (PEs) which function as ASBRs at the logical outer edge of the provider network, as well as provider (P) devices situated within the interior (“core”) of the provider network. Accordingly, each customer site contains at least one customer edge device (CE) coupled to a PE in the provider network. The customer site may be multi-homed to the provider network, i.e., wherein one or more of the customer's CEs is coupled to a plurality of PEs. The PE-CE data links may be established over various physical media, such as conventional wire links, optical links, wireless links, etc., and may communicate data formatted using various network communication protocols including ATM, Frame Relay, Ethernet, Fibre Distributed Data Interface (FDDI), etc.
In a popular VPN deployment, provider networks often provide the customer sites with layer-3 network-based VPN services that utilize IP and/or Multi-Protocol Label Switching (MPLS) technologies. These networks are typically said to provide “MPLS/VPN” services. This widely-deployed MPLS/VPN architecture is generally described in more detail in the IETF publication RFC 2547, entitled BGP/MPLS VPNs, by E. Rosen et al., published March 1999, which is hereby incorporated by reference as though fully set forth herein.
Most typically, PEs and CEs are configured to exchange routing information over their respective PE-CE data links in accordance with the Border Gateway Protocol (BGP). The BGP protocol is well known and described in detail in RFC 1771 by Y. Rekhter and T. Li, entitled A Border Gateway Protocol 4 (BGP-4), dated March 1995, which publication is hereby incorporated by reference as though fully set forth herein. A variation of the BGP protocol, known as internal BGP (iBGP), is often used to distribute routing and reachability information between PEs in the provider network. To implement iBGP, the PEs must be “fully meshed,” such that each PE is coupled to every other PE, e.g., by way of a Transmission Control Protocol (TCP) connection. Those skilled in the art will understand that the fully-meshed PEs may be directly connected or may be otherwise coupled, e.g., by one or more conventional BGP route reflectors.
BGP-enabled PEs and CEs perform various routing functions, including transmitting and receiving BGP messages or advertisements, and rendering routing decisions based on BGP routing policies. Each BGP-enabled device maintains a local BGP routing table that lists feasible routes to reachable (i.e., accessible) network nodes and subnetworks. The BGP table also may associate one or more BGP attributes with each route that it stores. For example, a conventional BGP AS-path attribute may be associated with a BGP route so as to identify a particular AS path that may be used for reaching that route. Typically, the AS path is represented as an ordered sequence of AS numbers corresponding to which ASes must be traversed in order to reach the route's associated node or subnetwork.
Although BGP is most often executed over PE-CE data links, other protocols also may be used to exchange routing and topology information between a customer-site CE and a provider-network PE. For instance, the Internet Draft publication <draft-ietf-13vpn-ospf-2547-05.txt>, entitled OSPF as the Provider/Customer Edge Protocol for BGP/MPLS IP VPNs, published November 2005 by Rosen et al., which publication is publicly available through the IETF and is hereby incorporated by reference in its entirety, describes an implementation in which OSPF is executed over a PE-CE link. In this case, the PE functions as an ABR for the customer site containing the CE, and thus the PE maintains both an OSPF LSDB containing the customer site's IGP topology information as well as a BGP table containing BGP routes that have been distributed, e.g., via iBGP, within the provider network.
One particular advantage to using IGP protocols (e.g., OSPF) as the PE-CE protocol for MPLS VPN networks is that the routing information from one customer network is kept “transparent” through the provider network into another customer network of the same IGP domain. In other words, because the PEs actively participate in the IGP sessions of the customer networks, each PE receives IGP messages advertising the VPN routes (i.e., IGP routes of a customer network) of the customer network from a CE (e.g., a first CE). Notably, in this manner, the PE is aware of the customer network's topology and possibly any metrics (e.g., cost, etc.) associated with the VPN routes. The PE (a first PE) may then propagate the VPN routes throughout the provider network, e.g., using BGP (e.g., iBGP or MP-BGP). In particular, in accordance with the above-incorporated Internet draft, entitled OSPF as the Provider/Customer Edge Protocol for BGP/MPLS IP VPNs, the PE may convert the IGP metrics and other topology information (domain identifiers, route types, etc.) into non-transitive extended community attributes. Once another PE (a second PE) receives the routes, the second PE determines whether it is attached to a customer network that belongs to the first CE's IGP domain. If so, the second PE converts the received BGP advertisement (e.g., and any non-transitive extended community attributes) into an IGP message for internal routes for the VPN (e.g., an OSPF Type 3 LSA) and forwards the IGP message to that CE (e.g., a second CE). Because the second CE receives an IGP message of internal routes, the second CE and subsequent nodes/routers of its customer network install the VPN routes as internal routes. The routing information from one customer network to another (e.g., of the same IGP domain) is thus kept “transparent” through the provider network, in that both customer networks view the advertised VPN routes as internal routes, regardless of the fact that the routes traverse the provider network (e.g., label switched).
Generally, however, many service providers prefer to use BGP as the PE-CE protocol, and force the customer networks to use BGP to announce their VPN routes to the PE. For instance, many service providers have better knowledge (comfort) of BGP, and BGP offers better control and/or policy over the customer's CEs. Some service provider PEs may not be able to communicate with certain IGPs, e.g., proprietary IGPs, such as the Enhanced Interior Gateway Routing Protocol (EIGRP) of Cisco Systems, Inc. (Those skilled in the art will understand that some customers would prefer to maintain privacy of their topology from the provider networks.) Also, BGP is more scalable than certain IGPs, which may require multiple IGP instances when the PE is attached to more than one CE (e.g., one IGP per customer VPN). Other reasons for using BGP as the PE-CE protocol will be understood by those skilled in the art, e.g., smaller LSDBs, BGP prefix limits, etc.
By using BGP as the PE-CE protocol, though, the transparency described above is destroyed. For instance, here the first CE will advertise its VPN routes to the first PE via a BGP advertisement, which is propagated to the second PE as mentioned above. Now, however, the second PE sends the VPN routes to the second CE as a BGP advertisement in accordance with the PE-CE protocol. As a result, the second CE converts the BGP advertisement into an IGP advertisement, and accordingly redistributes the routes into the customer network as external routes (e.g., as OSPF Type 5 LSAs), i.e., due to the conventional configuration that routes received via BGP are external routes as will be understood by those skilled in the art. The VPN routes that are actually internal to the second CE's IGP domain (i.e., and the first CE's IGP domain) are therefore improperly installed as external routes.
In addition to improperly installing internal VPN routes as external routes, any IGP attributes originally sent by the first CE to the first PE through the BGP advertisement will have been lost in the BGP transitions. For instance, certain IGP attributes may be encapsulated within a BGP advertisement. For example, those skilled in the art will understand how a multi-exit discriminator (MED) field within the BGP advertisement may be used to convey an IGP metric/cost value to the receiving node. The MED field, just as all other conventional fields currently used to convey IGP attributes, are non-transitive, in that they only enter the next AS (e.g., the provider network), but do not leave that AS (e.g., into other customer networks). As such, the second PE, when sending a BGP advertisement to the second CE (i.e., the next AS), will remove any non-transitive attributes, including any IGP attributes contained therein. Currently, no transitive attributes are available in BGP advertisements that would convey IGP attributes of a first customer network to another customer network.
There remains a need, therefore, for a technique that maintains IGP transparency of VPN routes when BGP is used as the PE-CE protocol. In particular, there remains a need to properly distinguish between internal VPN routes and external VPN routes at CEs receiving BGP advertisements. In addition, there remains a need to convey IGP attributes of those internal VPN routes of one customer network to another customer network using BGP advertisements.